package bin_tree.heap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * 基于整型的最大堆实现
 * 根节点从0开始编号，若此时节点编号为k
 * 左子树节点：2k + 1
 * 右子树节点：2k + 2
 * 父节点：（k - 1）/ 2
 */
public class MaxHeap {
    //使用JDK的动态数组来存储最大堆
    List<Integer> data;

    public MaxHeap() {
        //无参构造，默认长度为10
        this(10);
    }

    public MaxHeap(int size) {
        //有参构造，初始化堆大小
        this.data = new ArrayList<>(size);
    }

    /**
     * 数组的堆化操作
     *
     * @param arr
     */
    public MaxHeap(int[] arr) {
        data = new ArrayList<>(arr.length);
        // 1.将数组元素复制到data数组中
        for (int i : arr) {
            data.add(i);
        }
        // 2.从最后一个非叶子节点进行下沉操作
        for (int i = (data.size() - 1 - 1) / 2; i >= 0; i--) {
            siftDown(i);
        }
    }

    //查看最大元素
    public int peekMax() {
        if (isEmpty()) {
            throw new NoSuchElementException("heap is empty!cannot peek");
        }
        return data.get(0);
    }

    //元素添加操作
    public void add(int val) {
        //1.将元素添加到数组末尾
        data.add(val);
        //2.元素的上浮操作
        siftUp(data.size() - 1);
    }

    /**
     * 上浮操作
     * 上浮终止条件：已经走到根节点 || 当前节点值 <= 父节点值
     *
     * @param k
     */
    private void siftUp(int k) {
        //此时还没走到根节点 ｜｜ 当前元素 > 父节点元素
        while (k > 0 && data.get(k) > data.get(parent(k))) {
            //将当前节点位置与父节点位置交换
            swap(k, parent(k));
            k = parent(k);
        }
    }

    /**
     * 删除堆中最大值，即取出堆顶元素
     *
     * @return
     */
    public int extractMax() {
        //判空
        if (isEmpty()) {
            throw new NoSuchElementException("heap is empty!cannot extract!");
        }
        //1.获取最大值
        int max = data.get(0);
        //2.将数组末尾元素顶到堆顶
        int value = data.get(data.size() - 1);
        data.set(0, value);
        //3.删除末尾元素删除
        data.remove(data.size() - 1);
        //4.堆顶元素下沉操作
        siftDown(0);
        return max;
    }

    /**
     * 下沉操作
     * 终止条件： 2k + 1 > size || 当前节点值 > 左右子树的值
     *
     * @param k
     */
    private void siftDown(int k) {
        //还存在子树
        while (leftChild(k) < data.size()) {
            int j = leftChild(k);
            //判断一下是否有右子树，如果有判断左右子树大小
            if (j + 1 < data.size() && data.get(j + 1) > data.get(j)) {
                //此时右树存在且大于左树
                j = j + 1;
            }
            //此时j就是该节点左右子树最大值
            //将该节点值与最大值比较
            if (data.get(k) >= data.get(j)) {
                //此时下沉结束，退出循环
                break;
            }
            if (data.get(k) < data.get(j)) {
                //节点值小于左右子树最大值
                //进行下沉
                swap(k, j);
                k = j;
            }
        }
    }

    /**
     * 元素位置交换
     *
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        int temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

    //判空
    public boolean isEmpty() {
        return data.size() == 0;
    }

    //根据索引得到父节点的索引
    public int parent(int k) {
        return (k - 1) >> 1;
    }

    //根据索引得到左子树索引
    public int leftChild(int k) {
        return (k << 1) + 1;
    }

    //根据索引得到右子树索引
    public int rightChild(int k) {
        return (k << 1) + 2;
    }

    @Override
    public String toString() {
        return data.toString();
    }
}
